﻿// Spun AJAX Framework
// Copyright (C) 2008 Blake Hegerle
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Formality
{
    public class Graph
    {
        public static IEnumerable<T> Reachable<T>(T Start, Func<T, IEnumerable<T>> EdgeFunction)
        {
            return Reachable(Start.Singleton(), EdgeFunction);
        }

        public static IEnumerable<T> Reachable<T>(IEnumerable<T> StartingSubGraph, Func<T, IEnumerable<T>> EdgeFunction)
        {
            return Recursion.Cocombinator
                <T, IEnumerable<T>, IEnumerable<T>, IEnumerable<T>>
            (
                (rsingle, rmany)
                    => N
                        => N.Singleton().Union(rmany(EdgeFunction(N))),

                (rmany, rsingle)
                    => G
                        => from sg in
                               (from N in G select rsingle(N))
                           from N in sg
                           select N,

                m => m.MarkAndSweep(new T[0]), m => m
            ).Second(StartingSubGraph).Distinct();
        }
    }
}
